{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Earliest Possible Day of Full Bloom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: earliestFullBloom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #全部开花的最早一天"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有 <code>n</code> 枚花的种子。每枚种子必须先种下，才能开始生长、开花。播种需要时间，种子的生长也是如此。给你两个下标从 <strong>0</strong> 开始的整数数组 <code>plantTime</code> 和 <code>growTime</code> ，每个数组的长度都是 <code>n</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>plantTime[i]</code> 是 <strong>播种</strong> 第 <code>i</code> 枚种子所需的 <strong>完整天数</strong> 。每天，你只能为播种某一枚种子而劳作。<strong>无须</strong> 连续几天都在种同一枚种子，但是种子播种必须在你工作的天数达到 <code>plantTime[i]</code> 之后才算完成。</li>\n",
    "\t<li><code>growTime[i]</code> 是第 <code>i</code> 枚种子完全种下后生长所需的 <strong>完整天数 </strong>。在它生长的最后一天 <strong>之后</strong> ，将会开花并且永远 <strong>绽放</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>从第 <code>0</code> 开始，你可以按 <strong>任意</strong> 顺序播种种子。</p>\n",
    "\n",
    "<p>返回所有种子都开花的 <strong>最早</strong> 一天是第几天。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/21/1.png\" style=\"width: 453px; height: 149px;\">\n",
    "<pre><strong>输入：</strong>plantTime = [1,4,3], growTime = [2,3,1]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。\n",
    "一种最优方案是：\n",
    "第 0 天，播种第 0 枚种子，种子生长 2 整天。并在第 3 天开花。\n",
    "第 1、2、3、4 天，播种第 1 枚种子。种子生长 3 整天，并在第 8 天开花。\n",
    "第 5、6、7 天，播种第 2 枚种子。种子生长 1 整天，并在第 9 天开花。\n",
    "因此，在第 9 天，所有种子都开花。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/21/2.png\" style=\"width: 454px; height: 184px;\">\n",
    "<pre><strong>输入：</strong>plantTime = [1,2,3,2], growTime = [2,1,2,1]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>灰色的花盆表示播种的日子，彩色的花盆表示生长的日子，花朵表示开花的日子。 \n",
    "一种最优方案是：\n",
    "第 1 天，播种第 0 枚种子，种子生长 2 整天。并在第 4 天开花。\n",
    "第 0、3 天，播种第 1 枚种子。种子生长 1 整天，并在第 5 天开花。\n",
    "第 2、4、5 天，播种第 2 枚种子。种子生长 2 整天，并在第 8 天开花。\n",
    "第 6、7 天，播种第 3 枚种子。种子生长 1 整天，并在第 9 天开花。\n",
    "因此，在第 9 天，所有种子都开花。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>plantTime = [1], growTime = [1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>第 0 天，播种第 0 枚种子。种子需要生长 1 整天，然后在第 2 天开花。\n",
    "因此，在第 2 天，所有种子都开花。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == plantTime.length == growTime.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= plantTime[i], growTime[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [earliest-possible-day-of-full-bloom](https://leetcode.cn/problems/earliest-possible-day-of-full-bloom/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [earliest-possible-day-of-full-bloom](https://leetcode.cn/problems/earliest-possible-day-of-full-bloom/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,3]\\n[2,3,1]', '[1,2,3,2]\\n[2,1,2,1]', '[1]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for plant, grow in zip(plantTime, growTime):\n",
    "            d[grow ] += plant\n",
    "        max_time = 0\n",
    "        total_plant_time = 0\n",
    "        for grow in sorted(d.keys(), reverse=True):\n",
    "            total_plant_time += d[grow]\n",
    "            max_time = max(max_time, total_plant_time + grow)\n",
    "        return max_time "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "#         day,ans=0,0\n",
    "#         for i,j in sorted(zip(plantTime,growTime),key=lambda x:-x[1]):\n",
    "#             day+=i\n",
    "#             ans=max(ans,day+j)\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for plant, grow in zip(plantTime, growTime):\n",
    "            d[grow ] += plant\n",
    "        max_time = 0\n",
    "        total_plant_time = 0\n",
    "        for grow in sorted(d.keys(), reverse=True):\n",
    "            total_plant_time += d[grow]\n",
    "            max_time = max(max_time, total_plant_time + grow)\n",
    "        return max_time "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            pre = defaultdict(int)\n",
    "            pre[0] = 0\n",
    "            for p, g in zip(plantTime, growTime):\n",
    "                if x - g < 0:\n",
    "                    return False\n",
    "                pre[x - g] += p\n",
    "            pre = sorted([[v, k] for k, v in pre.items()], key=lambda x: x[1])\n",
    "            for i in range(1, len(pre)):\n",
    "                pre[i][0] += pre[i - 1][0]\n",
    "                if pre[i][0] > pre[i][1]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        left, right = sum(plantTime) + min(growTime), sum(plantTime) + max(growTime)\n",
    "        ans = right\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(growTime)\n",
    "        idx = [i for i in range(n)]\n",
    "        idx.sort(key=lambda x : growTime[x],reverse = True)\n",
    "        res = 0\n",
    "        pt = 0\n",
    "        for _ , i in enumerate(idx):\n",
    "            pt += plantTime[i]\n",
    "            res = max(res,pt + growTime[i] + 1)\n",
    "        return res -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(growTime)\n",
    "        index = sorted(range(len(growTime)), key=lambda k: growTime[k])\n",
    "        #combie = [[plantTime[i],growTime[i]] for i in range(n)]\n",
    "        #combie.sort(key=lambda x:x[1])\n",
    "        acc = growTime[index[0]]\n",
    "        for i in range(1,n):\n",
    "            acc = max(acc + plantTime[index[i-1]], growTime[index[i]])\n",
    "            pass\n",
    "        acc += plantTime[index[-1]]\n",
    "        return acc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        order = list(range(len(plantTime)))\n",
    "        order.sort(key=lambda x : growTime[x], reverse=True)\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for idx in order:\n",
    "            cur += plantTime[idx]\n",
    "            res = max(res, cur + growTime[idx])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        index = [i for i in range(len(plantTime))]\n",
    "        index.sort(key=lambda x:growTime[x])\n",
    "        tot_plant = sum(plantTime)\n",
    "        ans = 0\n",
    "        for idx in index:\n",
    "            ans = max(tot_plant + growTime[idx], ans)\n",
    "            tot_plant -= plantTime[idx]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        N = len(growTime)\n",
    "        grow_sort = sorted(range(N), key=lambda x: growTime[x], reverse=True)\n",
    "        print(grow_sort)\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in grow_sort:\n",
    "            s += plantTime[i]\n",
    "            ans = max(ans, s + growTime[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        idx = [i for i in range(len(growTime))]\n",
    "        idx = sorted(idx,key = lambda x:growTime[x],reverse = True)\n",
    "        res = 0\n",
    "        pt = 0\n",
    "        for id in idx:\n",
    "            pt += plantTime[id]\n",
    "            res = max(res,pt+growTime[id])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(reverse=True, key=lambda x: growTime[x])\n",
    "        ans = float('-inf')\n",
    "        pre_sum = 0\n",
    "        print(ind)\n",
    "        for i in range(n):\n",
    "            pre_sum += plantTime[ind[i]]\n",
    "            ans = max(ans, pre_sum + growTime[ind[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        no = [i for i in range(n)]\n",
    "        no = list(sorted(no, key=lambda x:growTime[x], reverse=True))\n",
    "        # print(no)\n",
    "        x = 0\n",
    "        res = 0\n",
    "        for idx in no:\n",
    "            x += plantTime[idx]\n",
    "            res = max(res, x + growTime[idx])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        total_tmp = []\n",
    "        gt_tmp = []\n",
    "        for p_i in range(len(plantTime)):\n",
    "            pt = plantTime[p_i]\n",
    "            gt = growTime[p_i]\n",
    "            gt_tmp.append(gt)\n",
    "            total_tmp.append(pt + gt)\n",
    "\n",
    "        gt_tmp = sorted(gt_tmp)[::-1]\n",
    "        total_tmp = sorted(total_tmp)[::-1]\n",
    "        \n",
    "        cur_time = 0\n",
    "        max_time = 0\n",
    "        idx = 0\n",
    "        kk = 0\n",
    "        pre = gt_tmp[0]\n",
    "        for long in gt_tmp:\n",
    "            cur_time += (idx - kk) * (pre - long)\n",
    "            while idx < len(total_tmp):\n",
    "                if long < total_tmp[idx]:\n",
    "                    cur_time += total_tmp[idx] - long\n",
    "                    idx += 1\n",
    "                else:\n",
    "                    max_time = max(cur_time + long, max_time)\n",
    "                    break\n",
    "            if idx == len(total_tmp):\n",
    "                max_time = max(cur_time + long, max_time)\n",
    "            pre = long\n",
    "            kk += 1\n",
    "\n",
    "        return max_time\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        res = 0\n",
    "        start = 0\n",
    "        n = len(growTime)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key = lambda x: growTime[x], reverse = True)\n",
    "        for i in range(n):\n",
    "            res = max(res, start + plantTime[idx[i]] + growTime[idx[i]])\n",
    "            start += plantTime[idx[i]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        plants=list(zip(growTime,plantTime))\n",
    "        plants.sort(reverse=True)\n",
    "        latestBloom=0 \n",
    "        now=0\n",
    "        for growTime, plantTime in plants:\n",
    "            now+=plantTime\n",
    "            latestBloom=max(latestBloom,now+growTime)\n",
    "        return latestBloom\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        times = sorted(zip(growTime, plantTime), reverse=True)\n",
    "        plantSum = 0\n",
    "        result = 0\n",
    "        for gt,pt in times:\n",
    "            plantSum += pt\n",
    "            result = max(result, plantSum+gt)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        total_tmp = []\n",
    "        gt_tmp = []\n",
    "        for p_i in range(len(plantTime)):\n",
    "            pt = plantTime[p_i]\n",
    "            gt = growTime[p_i]\n",
    "            gt_tmp.append(gt)\n",
    "            total_tmp.append(pt + gt)\n",
    "\n",
    "\n",
    "        gt_tmp = sorted(gt_tmp)[::-1]\n",
    "        total_tmp = sorted(total_tmp)[::-1]\n",
    "\n",
    "        print('gt_tmp = ', gt_tmp)\n",
    "\n",
    "        print('total_tmp = ', total_tmp)\n",
    "        \n",
    "        cur_time = 0\n",
    "        max_time = 0\n",
    "        idx = 0\n",
    "        kk = 0\n",
    "        pre = gt_tmp[0]\n",
    "        for long in gt_tmp:\n",
    "            cur_time += (idx - kk) * (pre - long)\n",
    "            while idx < len(total_tmp):\n",
    "                if long < total_tmp[idx]:\n",
    "                    cur_time += total_tmp[idx] - long\n",
    "                    idx += 1\n",
    "                else:\n",
    "                    max_time = max(cur_time + long, max_time)\n",
    "                    break\n",
    "            if idx == len(total_tmp):\n",
    "                max_time = max(cur_time + long, max_time)\n",
    "            # print('cur_time = ', cur_time, long)\n",
    "            pre = long\n",
    "            kk += 1\n",
    "\n",
    "        return max_time\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        st = SortedList()\n",
    "        for i,j in zip(growTime, plantTime):\n",
    "            st.add((i,j))\n",
    "        ptime, total = 0,0 \n",
    "        while st:\n",
    "            gt,pt = st.pop()\n",
    "            ptime+=pt \n",
    "            total = max(total,ptime+gt)\n",
    "        return total\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        idxs = sorted(range(n),key=lambda x:growTime[x],reverse=True)\n",
    "        res = -inf\n",
    "        begin = 0\n",
    "        for i in idxs:\n",
    "            begin += plantTime[i]\n",
    "            res = max(res,begin+growTime[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        sort_idx = sorted(range(len(growTime)), key=lambda x: growTime[x], reverse=True)\n",
    "        late_time, last_plant = 0, 0\n",
    "        for idx in sort_idx:\n",
    "            late_time = max(late_time, last_plant + plantTime[idx] + growTime[idx])\n",
    "            last_plant += plantTime[idx]\n",
    "        return late_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        l = [i for i in range(len(plantTime))]\n",
    "        l.sort(key=lambda i: growTime[i], reverse=True)\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        for i in l:\n",
    "            res = max(res, cur + growTime[i] + plantTime[i])\n",
    "            cur += plantTime[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        ind = [i for i in range(n)]\n",
    "        ind.sort(key=lambda x: growTime[x],reverse=True)\n",
    "        plant=[plantTime[_] for _ in ind]\n",
    "        growTime.sort(reverse=True)\n",
    "        a=0\n",
    "        m=0\n",
    "        for i in range(len(plant)):\n",
    "            a+=plant[i]\n",
    "            if a+growTime[i]>m:\n",
    "                m=a+growTime[i]\n",
    "        return m\n",
    "        \n",
    "        return min([])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        index = [i for i in range(n)]\n",
    "        index.sort(key=lambda i:growTime[i])\n",
    "        l = sum(plantTime)\n",
    "        ans = l\n",
    "        for i in index:\n",
    "            ans = max(ans, l + growTime[i])\n",
    "            l -= plantTime[i]\n",
    "            #print(ans, l, i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(growTime)\n",
    "        indices = list(range(n))\n",
    "        indices = sorted(indices, key=lambda x:growTime[x], reverse=True)\n",
    "        plant_time = plantTime[indices[0]]\n",
    "        bloom_time = growTime[indices[0]]\n",
    "        for i in indices[1:]:\n",
    "            plant_time += plantTime[i]\n",
    "            bloom_time = max(bloom_time - plantTime[i], growTime[i])\n",
    "        return plant_time + bloom_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        def compare_fn(i: int, j: int) -> int:\n",
    "            if growTime[i] > growTime[j]:\n",
    "                return -1\n",
    "            if growTime[i] < growTime[j]:\n",
    "                return 1\n",
    "            return 0\n",
    "        \n",
    "        n = len(plantTime)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=cmp_to_key(compare_fn))\n",
    "        \n",
    "        prev = ans = 0\n",
    "        for i in idx:\n",
    "            ans = max(ans, prev + plantTime[i] + growTime[i])\n",
    "            prev += plantTime[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        plantlist = sorted([i for i in range(n)], key = lambda x:growTime[x])\n",
    "        first = sum(plantTime) + growTime[plantlist[0]]\n",
    "        time = sum(plantTime)\n",
    "        for i in plantlist:\n",
    "            new = time + growTime[i]\n",
    "            if new > first:\n",
    "                first = new\n",
    "            time -= plantTime[i]\n",
    "        else:\n",
    "            return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        plantlist = sorted([i for i in range(n)], key = lambda x:growTime[x])\n",
    "        first = sum(plantTime) + growTime[plantlist[0]]\n",
    "        time = sum(plantTime)\n",
    "        for i in plantlist:\n",
    "            new = time + growTime[i]\n",
    "            if new > first:\n",
    "                first = new\n",
    "            time -= plantTime[i]\n",
    "            print(first)\n",
    "        else:\n",
    "            return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def earliestFullBloom(self, plantTime, growTime):\n",
    "        st = list(zip(growTime, plantTime))\n",
    "        st.sort(reverse=True)\n",
    "        last_grow = 0\n",
    "        time = 0\n",
    "        for g, p in st:\n",
    "            if p >= last_grow:\n",
    "                time += p - last_grow + g\n",
    "                last_grow = g\n",
    "            else:\n",
    "                if last_grow - p >= g:\n",
    "                    last_grow -= p\n",
    "                else:\n",
    "                    time += g - (last_grow - p)\n",
    "                    last_grow = g\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        gps = [(growTime[i], p) for i, p in enumerate(plantTime)]\n",
    "        gps.sort(reverse=True)\n",
    "        ans = t = 0\n",
    "        for g, p in gps:\n",
    "            t += p\n",
    "            ans = max(ans, t + g)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        a = [(growTime[i], plantTime[i]) for i in range(n)]\n",
    "        a.sort(reverse=True)\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for g, p in a:\n",
    "            s += p\n",
    "            ans = max(ans, s + g)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        s = SortedList()\n",
    "        for p, g in zip(plantTime, growTime):\n",
    "            s.add((g, p))\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        n = len(plantTime)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur += s[i][1]\n",
    "            ans = max(ans, cur + s[i][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        plants = sorted(zip(growTime, plantTime), reverse = True)\n",
    "        days = 0\n",
    "        ans = 0\n",
    "        for g, p in plants:\n",
    "            days += p \n",
    "            ans = max(ans, days + g)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n=len(plantTime)\n",
    "        temp=list(range(n))\n",
    "        temp.sort(key=lambda x: -growTime[x] )\n",
    "        ans=0\n",
    "        cur=0\n",
    "        for i in temp:\n",
    "            cur+=plantTime[i]\n",
    "            ans=max(ans,cur+growTime[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        # growTime[i] 大的先种\n",
    "        n = len(growTime)\n",
    "        arr = [i for i in range(n)]\n",
    "        arr.sort(key=lambda x: -growTime[x])\n",
    "        ans = total = 0\n",
    "        for i in arr:\n",
    "            p = plantTime[i]\n",
    "            g = growTime[i]\n",
    "            ans = max(ans, total + p + g)\n",
    "            total += p\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        f = list(zip(plantTime,growTime))\n",
    "        f.sort(key = lambda x: x[1],reverse = True)\n",
    "        ans = 0\n",
    "        pt = 0\n",
    "        for p,g in f:\n",
    "            pt+=p\n",
    "            ans = max(ans, pt + g)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        sorted_times = sorted(zip(plantTime, growTime), key = lambda x : x[1], reverse = True)\n",
    "        ans = pre = 0\n",
    "        for p, g in sorted_times:\n",
    "            pre += p\n",
    "            ans = max(ans, pre + g)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        # 贪心 先种生长时间长的\n",
    "        n = len(plantTime)\n",
    "        rec = [(plantTime[i], growTime[i]) for i in range(n)]\n",
    "        rec.sort(key=lambda x:x[1], reverse=True)\n",
    "        end = 0\n",
    "        start = 0\n",
    "        for i in range(n):\n",
    "            cur_end = start+rec[i][0]+rec[i][1]\n",
    "            end = max(end, cur_end)\n",
    "            start += rec[i][0]\n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        m = len(plantTime)\n",
    "        nums = [[g, p] for p, g in zip(plantTime, growTime)]\n",
    "        nums.sort(reverse=True)\n",
    "        start = -1\n",
    "        end = 0\n",
    "        for e, s in nums:\n",
    "            start += s\n",
    "            end = max(end, start + e)\n",
    "\n",
    "        return end + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n=len(plantTime)\n",
    "        comb=[]\n",
    "        for i in range(n):\n",
    "            comb.append([growTime[i],plantTime[i]])\n",
    "        comb.sort(reverse=True)\n",
    "        max_sum=comb[n-1][0]+comb[n-1][1]\n",
    "        for i in range(n-1,0,-1):\n",
    "            max_sum=max(max_sum,comb[i-1][0])+comb[i-1][1]\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        t = list(zip(plantTime, growTime))\n",
    "        l = sorted(t, reverse=True, key=lambda t: t[1])\n",
    "        zuida=0\n",
    "        gong=0\n",
    "        for x,y in l:\n",
    "            gong+=x\n",
    "            zuida=max(zuida,gong+y)\n",
    "        return zuida\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        def compare_fn(i: int, j: int) -> int:\n",
    "            if growTime[i] > growTime[j]:\n",
    "                return -1\n",
    "            if growTime[i] < growTime[j]:\n",
    "                return 1\n",
    "            return 0\n",
    "        \n",
    "        n = len(plantTime)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=cmp_to_key(compare_fn))\n",
    "        \n",
    "        prev = ans = 0\n",
    "        for i in idx:\n",
    "            ans = max(ans, prev + plantTime[i] + growTime[i])\n",
    "            prev += plantTime[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        def compare_fn(i: int, j: int) -> int:\n",
    "            if growTime[i] > growTime[j]:\n",
    "                return -1\n",
    "            if growTime[i] < growTime[j]:\n",
    "                return 1\n",
    "            return 0\n",
    "        \n",
    "        n = len(plantTime)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=cmp_to_key(compare_fn))\n",
    "        \n",
    "        prev = ans = 0\n",
    "        for i in idx:\n",
    "            ans = max(ans, prev + plantTime[i] + growTime[i])\n",
    "            prev += plantTime[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        pg = [[g, p] for p, g in zip(plantTime, growTime)]\n",
    "        pg = sorted(pg, reverse=True)\n",
    "        to_ret = 0\n",
    "        base = 0\n",
    "        for g, p in pg :\n",
    "            base += p\n",
    "            to_ret = max(to_ret, base+g)\n",
    "        return to_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        tim=[[x,y] for x,y in zip(plantTime,growTime)]\n",
    "        tim.sort(key=lambda x:x[1],reverse=True)\n",
    "        result = pts=0\n",
    "\n",
    "        for pt,gt in tim:\n",
    "            pts+=pt\n",
    "            result=max(result,pts+gt)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        l = sorted([[growTime[i], plantTime[i]] for i in range(n)], reverse=True)\n",
    "        ans = prev = 0\n",
    "        for g, p in l:\n",
    "            ans = max(ans, prev + p + g)\n",
    "            prev += p\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        data = [(growTime[i], plantTime[i]) for i in range(n)]\n",
    "        data.sort(reverse=True)\n",
    "        pt, maxt = 0, 0\n",
    "        print(data)\n",
    "        for g, p in data:\n",
    "            pt += p \n",
    "            maxt = max(maxt, pt + g)\n",
    "        \n",
    "        return maxt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        # 先种成熟时间最长的 再种成熟时间短的\n",
    "        lis = [(g, -p) for g, p in zip(growTime, plantTime)]\n",
    "        lis.sort(reverse=True)\n",
    "        # ans = 0\n",
    "        use = 0 # 种植用时\n",
    "        res = 0 # 成长纯消耗时间\n",
    "\n",
    "        for g, p in lis:\n",
    "            p = -p\n",
    "            # 如果剩余时间可以种植和成长\n",
    "            if res >= p + g:\n",
    "                use += p # 种植时间增加\n",
    "                res -= p # 纯成长时间\n",
    "            # 如果剩余时间可以种植 但不够成长\n",
    "            elif res >= p:\n",
    "                use += p # 种植时间增加\n",
    "                res = max(g , g - (res - p)) # 纯成长时间\n",
    "            # 如果剩余时间不够种植 # 也不够成长\n",
    "            else:\n",
    "                use += p\n",
    "                res = g\n",
    "        \n",
    "        return use + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        items = sorted(zip(plantTime, growTime), key = lambda x: - x[1])\n",
    "        pre = 0\n",
    "        res = 0\n",
    "        for p, g in items:\n",
    "            pre += p \n",
    "            res = max(res, pre + g)\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "# 对于两枚生长天数相同的种子，由于无论按照何种顺序播种，这两枚种子的最晚开花时间都是相同的，因此无需考虑生长天数相同的种子的播种顺序，在排序时，仅需按生长天数从大到小排序。\n",
    "\n",
    "        if n==1:\n",
    "            return plantTime[0]+growTime[0]\n",
    "        ans = days =0\n",
    "        for p, g in sorted(zip(plantTime, growTime), key=lambda z: -z[1]):\n",
    "            days += p  # 累加播种天数,累计的播种天数是固定的\n",
    "            ans = max(ans, days + g)  # 再加上生长天数，就是这个种子的开花时间\n",
    "        return ans\n",
    "    # 生长天数从大到小的顺序播种\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        ans = days = 0\n",
    "        for p, g in sorted(zip(plantTime, growTime), key=lambda z: -z[1]):\n",
    "            days += p  # 累加播种天数\n",
    "            ans = max(ans, days + g)  # 再加上生长天数，就是这个种子的开花时间\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        grow = plan = 0\n",
    "        for gt, pt in sorted(zip(growTime, plantTime), key=lambda it:-it[0]):\n",
    "            plan += pt\n",
    "            grow = max(grow, plan + gt)\n",
    "        return grow\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        temp = []\n",
    "        for i in range(len(plantTime)):\n",
    "            temp.append((plantTime[i],growTime[i]))\n",
    "        temp.sort(key = lambda x: -x[1])\n",
    "        cmax = 0\n",
    "        cday = 0\n",
    "        for t in temp:\n",
    "            cday+=t[0]\n",
    "            if cday+t[1]>cmax:\n",
    "                cmax = cday+t[1]\n",
    "        return cmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        # 理想形态应该是\n",
    "        # 如果一个grow time很大，那么他应该更早被plant\n",
    "        # 播种时间结束最早是否意味着答案最优？\n",
    "        #   有没有可能播种时间结束最早但是生长周期最长的被最后播种？不可能，因为可以调节播种前后\n",
    "        #   if 存在方案 中减少一天不播种，但是最优，那么一定可以吧最后开花的那个植物往前挪一天\n",
    "        #   so答案一定是播种时间结束最早\n",
    "        # 播种时间结束最早后，是否是可以通过直接的数学计算确认？即如果一个植物的生长时间最长，那么他总是可以最先被播种\n",
    "        #   if 最优解中，因为生长时间最长a2的植物的播种时间也很长a1，先播种他会导致另一个植物b1, b2\n",
    "        #       即 a2>b2 a1 > b1 最优答案必须先播种b1，再播种a1, 但是b1+a1+a2 > a1+b1+b2所以不会\n",
    "        #  综上，总是 先播种时间最长的，播种时间合等于sum plant time\n",
    "        #       然后再根据growtime 从前往后放，取max(base + a1 +b1) base = sum(前面所有的plant time)\n",
    "        sum_plant_time = sum(plantTime)\n",
    "        growTime = [[t, i] for i, t in enumerate(growTime)]\n",
    "        growTime.sort(reverse=True)\n",
    "        base = 0\n",
    "        ans = 0\n",
    "        for t, i in growTime:\n",
    "            ans = max(ans, base + plantTime[i] + t)\n",
    "            base = base + plantTime[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        h = [(g, p) for g, p in zip(growTime, plantTime)]\n",
    "        h.sort(reverse=True)\n",
    "\n",
    "        pre = list(accumulate([t[1] for t in h]))\n",
    "        ans = 0\n",
    "        for i, v in enumerate(h):\n",
    "            ans = max(ans, pre[i] + v[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        grow = [(i, growTime[i]) for i in range(len(growTime))]\n",
    "        grow = sorted(grow, key = lambda x : x[1], reverse = True)\n",
    "        max_ = 0\n",
    "        cur = 0\n",
    "        for i in range(len(plantTime)):\n",
    "            cur += plantTime[grow[i][0]]\n",
    "            max_ = max(max_, cur + grow[i][1])\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        n = len(plantTime)\n",
    "        res = []\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            res.append([plantTime[i], growTime[i]])\n",
    "        res.sort(key = lambda x: -x[1])\n",
    "        for i in range(n):\n",
    "            cnt += res[i][0]\n",
    "            ans = max(ans, cnt + res[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        pg = [[plantTime[i], growTime[i]] for i in range(n)]\n",
    "        pg.sort(key=lambda x: -x[1])\n",
    "        res, plant = 0, 0\n",
    "        for i in range(n):\n",
    "            plant += pg[i][0]\n",
    "            res = max(res, plant + pg[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        fs = []\n",
    "        for p, g in zip(plantTime, growTime):\n",
    "            fs.append([g, p])\n",
    "        #print(fs[0][0])\n",
    "        fs.sort(key = lambda x: -x[0])\n",
    "        tot = sum(plantTime)\n",
    "        preSum = 0\n",
    "        ans = tot\n",
    "        for g, p in fs:\n",
    "            ans = max(ans, preSum + p + g)\n",
    "            preSum += p\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        ll = [[a, b] for a, b in zip(plantTime, growTime)]\n",
    "        ll.sort(key=lambda x: -x[1])\n",
    "        # print(ll)\n",
    "        n = len(ll)\n",
    "        cur = ll[0][0]\n",
    "        rem = ll[0][1]\n",
    "        ans = cur + rem\n",
    "        for i in range(1, n):\n",
    "            # print(cur, rem)\n",
    "            plant = ll[i][0]\n",
    "            grow = ll[i][1]\n",
    "            ans = max(ans, cur + plant + grow)\n",
    "            # if plant <= rem:\n",
    "                # rem -= plant\n",
    "            cur += plant\n",
    "            # else:\n",
    "                # cur += plant\n",
    "                # rem = grow\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        ll = [[a, b] for a, b in zip(plantTime, growTime)]\n",
    "        ll.sort(key=lambda x: -x[1])\n",
    "        # print(ll)\n",
    "        n = len(ll)\n",
    "        cur = ll[0][0]\n",
    "        rem = ll[0][1]\n",
    "        ans = cur + rem\n",
    "        for i in range(1, n):\n",
    "            # print(cur, rem)\n",
    "            plant = ll[i][0]\n",
    "            grow = ll[i][1]\n",
    "            ans = max(ans, cur + plant + grow)\n",
    "            if plant <= rem:\n",
    "                rem -= plant\n",
    "                cur += plant\n",
    "            else:\n",
    "                cur += plant\n",
    "                rem = grow\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        def compare_func(i: int, j: int) -> int:\n",
    "            if growTime[i] > growTime[j]:\n",
    "                return -1\n",
    "            if growTime[i] < growTime[j]:\n",
    "                return 1\n",
    "            return 0\n",
    "        n = len(plantTime)\n",
    "        idx = [i for i in range(n)]\n",
    "        allTime = plantTime.copy()\n",
    "        for i in range(n):\n",
    "            allTime[i] += growTime[i]\n",
    "\n",
    "        idx.sort(key=cmp_to_key(compare_func))\n",
    "        days, prev = 0, 0\n",
    "        for i in idx:\n",
    "            days = max(days, prev + plantTime[i] + growTime[i])\n",
    "            prev += plantTime[i]\n",
    "        return days"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "    n = len(plantTime)\n",
    "    order = list(range(n))\n",
    "    order.sort(key=lambda x: (-growTime[x], plantTime[x]))\n",
    "    day = 0\n",
    "    ans = 0\n",
    "    # print(order)\n",
    "    for i in order:\n",
    "      day += plantTime[i]\n",
    "      ans = max(ans, day + growTime[i])\n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        ids = list(range(n))\n",
    "        ids.sort(key=lambda id: (-growTime[id], plantTime[id]))\n",
    "        res = 0\n",
    "        end_time = 0\n",
    "        for id in ids:\n",
    "            end_time = end_time + plantTime[id]\n",
    "            res = max(res, end_time + growTime[id])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        lstp, lstg = zip(*sorted(zip(plantTime, growTime), key = lambda x : - x[1]))\n",
    "        return max(p + g for p, g in zip(accumulate(lstp), lstg))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        temp = []\n",
    "        for i in range(len(growTime)):\n",
    "            temp.append((-growTime[i], plantTime[i]))\n",
    "        temp.sort()\n",
    "        ans = []\n",
    "        s = 0\n",
    "        for i in range(len(temp)):\n",
    "            ans.append(s + temp[i][1] - temp[i][0])\n",
    "            s += temp[i][1]\n",
    "        return max(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        t = [(i, growTime[i]) for i in range(n)]\n",
    "        t.sort(key=lambda x:-x[1])\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for i, _ in t:\n",
    "            res=max(res, cur+growTime[i]+plantTime[i])\n",
    "            cur+=plantTime[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        idx = [i for i in range(n)]\n",
    "        idx.sort(key = lambda x:(-growTime[x], plantTime[x]))\n",
    "        day = 0\n",
    "        ans = 0\n",
    "        for i in idx:\n",
    "            day += plantTime[i]\n",
    "            ans = max(ans, day + growTime[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        res = now = 0\n",
    "        for p, g in sorted([(p, g) for p, g in zip(plantTime, growTime)], key = lambda f:(-f[1], f[0])): res, now = max(res, now + p + g), now + p\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        '''生长周期越长越早种'''\n",
    "        result = 0\n",
    "        plant = 0\n",
    "        order = []\n",
    "        for i,j in zip(plantTime,growTime):\n",
    "            order.append([-j,-i])\n",
    "        order.sort()\n",
    "        for i in order:\n",
    "            plant -= i[-1]\n",
    "            temp_time = plant-i[0]\n",
    "            result = max(result,temp_time)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        comTime = []\n",
    "        n = len(plantTime)\n",
    "        for i in range(n):\n",
    "            comTime.append([plantTime[i], growTime[i]])\n",
    "        def size(x):\n",
    "            return x[1]*10000 + x[0]\n",
    "        comTime.sort(key=size, reverse=True)\n",
    "\n",
    "        sumTime = [0] * n\n",
    "        sumTime[0] = comTime[0][0] + comTime[0][1]\n",
    "        for i in range(1, n):\n",
    "            comTime[i][0] += comTime[i-1][0]\n",
    "            sumTime[i] = comTime[i][0] + comTime[i][1]\n",
    "\n",
    "        return max(sumTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        nums = list(zip(plantTime,growTime))\n",
    "        nums.sort(key = lambda x: [-x[1], x[0]])\n",
    "        # p[0] = 1, g[0] = 3\n",
    "        # p[1] = 2, g[1] = 3\n",
    "        # p0 xx xx g0 g0 g0\n",
    "        # xx p0 p0 g0 g0 g0\n",
    "\n",
    "        res = 0\n",
    "        ps = 0\n",
    "        for p,g in nums:\n",
    "            ps += p\n",
    "            tmp = ps + g\n",
    "            if tmp > res:\n",
    "                res = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        grow = [[i, time] for i, time in enumerate(growTime)]\n",
    "        grow.sort(key= lambda x: -x[1])\n",
    "        res, pre = 0, 0\n",
    "        for i, time in grow:\n",
    "            pre += plantTime[i]\n",
    "            res = max(res, pre + time)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        grow = [[i, time] for i, time in enumerate(growTime)]\n",
    "        grow.sort(key= lambda x: -x[1])\n",
    "        res, pre = 0, 0\n",
    "        for i, time in grow:\n",
    "            res = max(res, pre + plantTime[i] + time)\n",
    "            pre += plantTime[i]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        l = len(plantTime)\n",
    "        a = []\n",
    "        for i in range(l):\n",
    "            a.append([plantTime[i], growTime[i]])\n",
    "        a.sort(reverse=True, key=lambda x: (x[1],x[0]))\n",
    "        plant, grow = 0, 0\n",
    "        for i in range(l):\n",
    "            plant += a[i][0]\n",
    "            grow = max(grow-a[i][0], a[i][1])\n",
    "        return plant+grow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        if self.y > other.y:\n",
    "            return True\n",
    "        elif self.y < other.y:\n",
    "            return False\n",
    "        else:\n",
    "            return self.x <= other.x\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        arr = []\n",
    "        for a, b in zip(plantTime, growTime):\n",
    "            heapq.heappush(arr, Node(a, b))\n",
    "        t = 0\n",
    "        cur = 0\n",
    "        while arr:\n",
    "            node = heapq.heappop(arr)\n",
    "            cur += node.x\n",
    "            t = max(t, cur+node.y)\n",
    "        return t\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:\n",
    "        n = len(plantTime)\n",
    "        arr = [[-growTime[i],plantTime[i],i] for i in range(n)]\n",
    "        arr.sort()\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for g,p,i in arr:\n",
    "            ans = max(ans, pre-g+p)\n",
    "            pre += p \n",
    "        return ans \n",
    "        def compare_fn(i: int, j: int) -> int:\n",
    "            if growTime[i] > growTime[j]:\n",
    "                return -1\n",
    "            if growTime[i] < growTime[j]:\n",
    "                return 1\n",
    "            return 0\n",
    "        \n",
    "        n = len(plantTime)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=cmp_to_key(compare_fn))\n",
    "        \n",
    "        prev = ans = 0\n",
    "        for i in idx:\n",
    "            ans = max(ans, prev + plantTime[i] + growTime[i])\n",
    "            prev += plantTime[i]\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/earliest-possible-day-of-full-bloom/solutions/1202113/quan-bu-kai-hua-de-zui-zao-yi-tian-by-le-ocxg/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
